package mianshi;

public class WorldSearch {

  private static int distract[][]=new int[][]{{0,1},{1,0},
                                              {0,-1},{-1,0}};
  public static void main(String[] args) {
	System.out.println(exist(new char[][]{{'a','b','c','e'},
			                              {'s','f','c','f'},
			                              {'a','d','e','e'}},"efa"));
}
   public static boolean exist(char[][] board, String word) {	
	   int vist[][]=new int[board.length][board[0].length];
	   
       for(int i=0;i<board.length;i++){
    	   for(int j=0;j<board[0].length;j++){
    		   if(board[i][j]==word.charAt(0)){
    			  if(isSearch(board,i,j,word,0,vist))
    				  return true;
    		   }
    	   }
       }
	   return false;
    }
private static boolean isSearch(char board[][],int i, int j, String word,int d,int vist[][]) {
          if(d==word.length()-1&&board[i][j]==word.charAt(d)){
        	  return true;
          }else if(board[i][j]==word.charAt(d)){
        	  vist[i][j]=-1;
        	  for(int k=0;k<4;k++){
        		  int n=i+distract[k][0];
        		  int m=j+distract[k][1];
        		  if(n>board.length-1||m>board[0].length-1||n<0||m<0)
        			  continue;
        		  else if(board[n][m]==word.charAt(d+1)&&vist[n][m]!=-1){
        			  boolean result=isSearch(board,n,m,word,d+1,vist);
        			  if(!result){
        				  continue;
        			  }else
        				  return result;
        		  }
        	  }
          }
          vist[i][j]=0;
		return false;
}
}
